/**416. 分割等和子集
 * - 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 */
export function canPartition(nums: number[]): boolean {
    /*
      背包的体积为sum / 2
      背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
      背包如果正好装满，说明找到了总和为 sum / 2 的子集。
      背包中每一个元素是不可重复放入。
     */
    //背包dp[j]   容量为j的背包，所背的物品价值最大可以为dp[j]。
    //递推公式是 dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
    const sum = nums.reduce((a, b) => a + b, 0)
    if (sum % 2 !== 0) return false
    const target = sum / 2
    const dp = new Array(target + 1).fill(0)
    // 为什么内层循环是逆序：因为i每加1代表新的一行开始，由于dp[j-num[i]]每次都得使用的是上一行的数据。但是如果你正序的话，那么你在计算dp[j]的时候用到的dp[j-num[i]]是本行的，而不是上一行的，所以用逆序，逆序用到的dp[j-num[i]]是上一行的。
    // 这里面的数字是无序的，所以每次你取一个nums[i]以后，进入嵌套的for循环都要先比较一下，是否这个数值小于我们的背包
    // 如果小于背包才可以继续往下。之前的背包问题，背包大小是单调递增的。
    for (let i = 0; i < nums.length; i++) {//遍历每个数字，重量和价值都是 nums[i]
        for (let j = target; j >= nums[i]; j--) {//从大到小遍历背包容量，且是从targe开始，nums[i]结束，看看这一个范围内哪个能放进背包
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
        }
    }
    return dp[target] === target
}
/**494. 目标和
 * - 给你一个非负整数数组 nums 和一个整数 target 。
 * - 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * - 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * - 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目
 */
export function findTargetSumWays(nums: number[], target: number): number {
    // 本题的集合总数sum肯定大于等于target的，这样才能通过搭配得到target。那么就转换为了，一部分是正子集(left)，一部分是负子集(right)
    // 所以left+right=sum，left-right=target  => 目标子集总和left = (sum + target) / 2

    // 和之前遇到的背包问题不一样，之前都是求容量为j的背包，最多能装多少。
    // 本题则是装满有几种方法。也就是一个组合问题了。

    /*
      dp[j] 代表当集合长度为j时，有几种方法  （填满j（包括j）这么大容积的包，有dp[j]种方法）
      dp[j] =  dp[j]  +  dp[j - nums[i]] + nums[i]   由于是组合问题，所以这里需要不断的增加
      例如：dp[j]，j 为5， 
      已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
      已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
      已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
      已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
      已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包
      那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
    */
    const sum = nums.reduce((pre, cur) => pre + cur)
    if ((sum + target) % 2 === 1 || Math.abs(target) > sum) return 0//如果sum+target是奇数，或target绝对值大于sum的话，无解
    const left = (sum + target) / 2
    const dp = new Array(left + 1).fill(0)
    dp[0] = 1//后面的数都是由这个推导出来的
    for (let i = nums.length - 1; i >= 0; i--) {
        for (let j = left; j >= nums[i]; j--) { //背包逆序遍历
            dp[j] += dp[j - nums[i]] //这个公式要记住
        }
    }
    return dp[left]
}